/*
 @coding  : utf-8
 @Time    : 2023/5/23 14:51
 @Author  : Rumou
 @File    : 20230523-找到两个叶子节点中最近的公共节点.go
 @Description:
*/

package main

import "fmt"

// TreeNode 定义二叉树结构体
type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

// FindClosestCommonNode 寻找两个叶子节点中最近的公共节点
func FindClosestCommonNode(root *TreeNode, leaf1 *TreeNode, leaf2 *TreeNode) *TreeNode {
	// 递归遍历左子树和右子树
	left := FindClosestCommonNode(root.Left, leaf1, leaf2)
	right := FindClosestCommonNode(root.Right, leaf1, leaf2)

	// 当前节点为叶子节点或为空时，返回当前节点
	if root == leaf1 || root == leaf2 || root == nil {
		return root
	}

	// 如果左子树和右子树分别包含两个叶子节点，当前节点为最近公共节点
	if left != nil && right != nil {
		return root
	}

	// 如果只有左子树包含叶子节点，返回左子树中的最近公共节点
	if left != nil {
		return left
	}

	// 如果只有右子树包含叶子节点，返回右子树中的最近公共节点
	if right != nil {
		return right
	}

	// 左右子树都不包含叶子节点，返回空
	return nil
}

func main() {
	tree := &TreeNode{
		Data: 1,
		Left: &TreeNode{
			Data: 2,
			Left: &TreeNode{
				Data:  4,
				Left:  nil,
				Right: nil,
			},
			Right: nil,
		},
		Right: &TreeNode{
			Data: 3,
			Left: nil,
			Right: &TreeNode{
				Data:  5,
				Left:  nil,
				Right: nil,
			},
		},
	}

	// 构建两个叶子节点
	leaf1 := &TreeNode{Data: 4}
	leaf2 := &TreeNode{Data: 5}

	// 查找
	result := FindClosestCommonNode(tree, leaf1, leaf2)

	// 输出
	if result != nil {
		fmt.Println("最近的公共节点:", result.Data)
	} else {
		fmt.Println("无公共节点")
	}
}
